# 1.定义数组元素的含义，清楚dp[i]的含义，表示的结果
# 2.找出数组元素的关系式，即动态转移方程，递进公式
# 3.找出初始值，例如第一个元素值


#回溯算法
ans = []
def trace(path,choices):
    if len(path) == len(nums):
        ans.append(list(path))

    for i in choices:
        if i in path:
            continue
        path.append(i)
        trace(path,choices)
        path.pop()
    return ans
nums = [1,2,3,4]
print(trace([],nums))

res = []
path = []
def bt(nums,startIndex):
    res.append(path[:])
    for i in range(startIndex,len(nums)):
        path.append(nums[i])
        bt(nums,i+1)
        path.pop()
nums = [1,2,3]
bt(nums,0)
print(res)